class Solution:
    def knightDialer(self, n: int) -> int:
        dp = [[0]*10 for i in range(n+1)]
        dp[1] = [1,1,1,1,1,1,1,1,1,1]
        jump = {0:[4, 6], 1:[6, 8], 2:[7, 9], 3:[4, 8], 4:[0, 3, 9], 5:[], 6:[0, 1, 7], 7:[2, 6], 8:[1, 3], 9:[2, 4]}
        for i in range(2, n+1):
            for j in range(10):
                if j == 5:
                    dp[i][j] = 0
                else:
                    for k in jump[j]:
                        dp[i][j] += dp[i-1][k]
        return sum(dp[n])

if __name__ == '__main__':
    print(Solution().knightDialer(1)) # 10
    print(Solution().knightDialer(2)) # 20
    print(Solution().knightDialer(3331))